import java.util.LinkedList;
import java.util.Queue;

class Solution02 {
    // 利用正难则反的思路
    /**
     * 先遍历四周
     */
    // 定义数轴 上下左右
    int[] dx = new int[] { 0, 0, -1, 1 };
    int[] dy = new int[] { 1, -1, 0, 0 };
    // 定义两个变量记录给的数组大小
    int m, n;

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        // 遍历上下边界
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                bfs(board, 0, i);
            }
            if (board[m - 1][i] == 'O') {
                bfs(board, m - 1, i);
            }
        }
        // 遍历左右边界
        for (int i = 1; i < m - 1; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                bfs(board, i, n - 1);
            }
        }

        // 还原
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '1') {
                    board[i][j] = 'O';
                }
            }
        }

    }

    // 定义好bfs
    public void bfs(char[][] board, int i, int j) {
        // 创建一个队列
        Queue<int[]> q = new LinkedList<>();
        // 入队
        q.offer(new int[] { i, j });
        board[i][j] = '1';

        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    board[x][y] = '1';
                    q.offer(new int[] { x, y });
                }
            }
        }
    }
}